//1:
//Given a sorted array, remove the duplicates in place such that each element appear only once
//and return the new length.
//Do not allocate extra space for another array, you must do this in place with constant memory.
//For example, Given input array A = [1, 1, 2],
//Your function should return length = 2, and A is now[1, 2].
#include<iostream>
#include<algorithm>
using namespace std;

class Solution{
public:
	int Remove_Duplicates(int arr[], int len)
	{
		int index = 0;
		for (int i = 1; i < len; i++)
		{
			if (arr[i] != arr[index])
			{
				arr[++index] = arr[i];
			}
		}
		return index+1;
	}
};

//class Solution{          //stl 目前没搞清楚
//public:
//	int Remove_Duplicates(int arr[], int len)
//	{
//		return distance(arr, unique(arr, arr + len));
//	}
//};

//2:
//Follow up for ¡±Remove Duplicates¡± : What if duplicates are allowed at most twice ?
//For example, Given sorted array A = [1, 1, 1, 2, 3, 4],
//Your function should return length = 5, and A is now[1, 1, 2, 2, 3]

class solution2{
public:
	int Remove_Duplicates(int arr[], int len)
	{
		if (len <=2)
		{
			return len;
		}
		int index = 2;
		for (int i = 2; i < len; i++)
		{
			if (arr[i]!=arr[index-2])
			{
				arr[index++] = arr[i];
			}
		}
		return index;
	}
};
int main()
{
	int arr1[10] = { 1, 3, 3, 5, 5, 6, 7, 8, 8, 9 };
	int arr2[10] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4 };
	Solution s;
	solution2 s2;
	cout << s.Remove_Duplicates(arr1, 10) << endl;
	cout << s2.Remove_Duplicates(arr2, 10) << endl;
	return 0;
}